<?php
/**
 * <https://y.st./>
 * Copyright © 2017 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Unit1.java',
	'<{subtitle}>' => 'Written in <span title="Programming 2">CS 1103</span> of <a href="http://www.uopeople.edu/">University of the People</a>, finalised on 2017-06-21',
	'<{copyright year}>' => '2017',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<h2>Source code:</h2>
<blockquote>
<pre><code>/* 
 * Copyright (C) 2017 Alex Yst
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see &lt;http://www.gnu.org/licenses/&gt;.
 */
/* 
 * Output of this program:
 * Seconds needed for insertionSort() to sort 1000 elements: 0.011
 * Seconds needed for selectionSort() to sort 1000 elements: 0.008
 * Seconds needed for java.util.Arrays.sort() to sort 1000 elements: 0.001
 * Seconds needed for insertionSort() to sort 10000 elements: 0.097
 * Seconds needed for selectionSort() to sort 10000 elements: 0.183
 * Seconds needed for java.util.Arrays.sort() to sort 10000 elements: 0.001
 * Seconds needed for insertionSort() to sort 100000 elements: 2.766
 * Seconds needed for selectionSort() to sort 100000 elements: 10.424
 * Seconds needed for java.util.Arrays.sort() to sort 100000 elements: 0.004
 */
package st.y.CS1103.Unit1;

/**
 * Alex Yst&apos;s CS 1103 (Programming 2) Unit 1 submission
 * 
 * This class compares three sorting algorithms; two defined in user space and
 * one built into the language.
 * 
 * @author Alex Yst
 */
public class Unit1 {
/**
 * This is the list of array lengths we&apos;ll test with.
 */
	final static int[] ARRAY_LENGTHS = {
		1000,
		10000,
		100000,
	};

/**
 * Main method
 * 
 * Sorting algorithms are compared here and their completion times are output.
 * 
 * @param args The command line arguments are ignored.
 */
	public static void main(String[] args) {
// We need to test this with three different lengths. Why not use a loop?
		for(int length : ARRAY_LENGTHS) {
			int[] insertionArray = new int[length];
			int[] selectionArray = new int[length];
			int[] regularArray = new int[length];
			for(int i=0;i&lt;length;i++) {
				int integer = (int)(Integer.MAX_VALUE * Math.random());
// These arrays should be identical to prevent any strangeness that could make
// one sorting algorithm falsely appear faster than it is.
				insertionArray[i] = integer;
				selectionArray[i] = integer;
				regularArray[i] = integer;
			}
			long insertionStartTime = System.currentTimeMillis();
			insertionSort(insertionArray);
			long insertionRunTime = System.currentTimeMillis() - insertionStartTime;
			System.out.print(&quot;Seconds needed for insertionSort() to sort &quot;);
			System.out.print(length);
			System.out.print(&quot; elements: &quot;);
			System.out.println(insertionRunTime/1000.0);
			long selectionStartTime = System.currentTimeMillis();
			selectionSort(selectionArray);
			long selectionRunTime = System.currentTimeMillis() - selectionStartTime;
			System.out.print(&quot;Seconds needed for selectionSort() to sort &quot;);
			System.out.print(length);
			System.out.print(&quot; elements: &quot;);
			System.out.println(selectionRunTime/1000.0);
			long regularStartTime = System.currentTimeMillis();
			java.util.Arrays.sort(insertionArray);
			long regularRunTime = System.currentTimeMillis() - regularStartTime;
			System.out.print(&quot;Seconds needed for java.util.Arrays.sort() to sort &quot;);
			System.out.print(length);
			System.out.print(&quot; elements: &quot;);
			System.out.println(regularRunTime/1000.0);
		}
	}

/**
 * Insertion Sort
 * 
 * This method uses an insertion sort to sort elements in an array of integers.
 * No value is returned and the original array is modified.
 * 
 * This method was copied from
 * &lt;http://math.hws.edu./eck/cs124/javanotes5/c7/s4.html&gt;. THis method, along
 * with the rest of the book that contains it, was released under the CC BY-SA
 * 2.5 license. According to the Creative Commons compatibility list, CC BY-SA
 * 2.5 works may be upgraded to be covered by version 4.0 of the same license,
 * and works under CC BY-SA are compatible with the GNU GPLv3. It is therefore
 * my understanding that I may incorporate this method into this GPLv3 class.
 * If you feel this is incorrect, please let me know and I&apos;ll do my best to
 * remedy the situation. For more information, the Creative Commons
 * compatibility list is available here:
 * &lt;https://creativecommons.org/share-your-work/licensing-considerations/compatible-licenses/&gt;.
 * 
 * @author David J. Eck
 * @param A The array to be sorted
 */
	public static void insertionSort(int[] A) {
// Sort the array A into increasing order.

		int itemsSorted; // Number of items that have been sorted so far.

		for (itemsSorted = 1; itemsSorted &lt; A.length; itemsSorted++) {
// Assume that items A[0], A[1], ... A[itemsSorted-1] 
// have already been sorted.  Insert A[itemsSorted]
// into the sorted part of the list.

			int temp = A[itemsSorted];  // The item to be inserted.
			int loc = itemsSorted - 1;  // Start at end of list.

			while (loc &gt;= 0 &amp;&amp; A[loc] &gt; temp) {
				A[loc + 1] = A[loc]; // Bump item from A[loc] up to loc+1.
				loc = loc - 1;       // Go on to next location.
			}

			A[loc + 1] = temp; // Put temp in last vacated space.
		}
	}

/**
 * Selection Sort
 * 
 * This method uses a selection sort to sort elements in an array of
 * integers. No value is returned and the original array is modified.
 * 
 * This method was copied from
 * &lt;http://math.hws.edu./eck/cs124/javanotes5/c7/s4.html&gt;. THis method, along
 * with the rest of the book that contains it, was released under the CC BY-SA
 * 2.5 license. According to the Creative Commons compatibility list, CC BY-SA
 * 2.5 works may be upgraded to be covered by version 4.0 of the same license,
 * and works under CC BY-SA are compatible with the GNU GPLv3. It is therefore
 * my understanding that I may incorporate this method into this GPLv3 class.
 * If you feel this is incorrect, please let me know and I&apos;ll do my best to
 * remedy the situation. For more information, the Creative Commons
 * compatibility list is available here:
 * &lt;https://creativecommons.org/share-your-work/licensing-considerations/compatible-licenses/&gt;.
 * 
 * @author David J. Eck
 * @param A The array to be sorted
 */
	public static void selectionSort(int[] A) {
// Sort A into increasing order, using selection sort

		for (int lastPlace = A.length-1; lastPlace &gt; 0; lastPlace--) {
// Find the largest item among A[0], A[1], ...,
// A[lastPlace], and move it into position lastPlace 
// by swapping it with the number that is currently 
// in position lastPlace.

			int maxLoc = 0; // Location of largest item seen so far.

			for (int j = 1; j &lt;= lastPlace; j++) {
				if (A[j] &gt; A[maxLoc]) {
// Since A[j] is bigger than the maximum we&apos;ve seen
// so far, j is the new location of the maximum value
// we&apos;ve seen so far.
					maxLoc = j;
				}
			}

			int temp = A[maxLoc]; // Swap largest item with A[lastPlace].
			A[maxLoc] = A[lastPlace];
			A[lastPlace] = temp;

		} // end of for loop

	}
}</code></pre>
</blockquote>
END
);
